package LeetCode;

import java.util.Arrays;
import java.util.*;
public class LeetCodeMain19 {
    public String longestCommonPrefix(String[] strs) {
        Arrays.sort(strs,(o1, o2) -> o1.length()-o2.length());
        String str="";
        for (int i = 0; i < strs[0].length(); i++) {
            String strs1=strs[0].substring(0,i+1);
            int flag=0;
            for (int j = 0; j < strs.length; j++) {
                if (strs1.equals(strs[j].substring(0,i+1))){
                    flag++;
                }
            }
            if (i==0&&flag!=strs.length){
                break;
            }
            if (flag== strs.length){
                str=strs1;
            }
        }
        return str;
    }
    public int[] searchRange(int[] nums, int target) {
        int[] tar=new int[2];
        Arrays.fill(tar,-1);
        tar[0]=binarySearch(nums,target,true);
        tar[1]=binarySearch(nums,target,false);
        return tar;
    }
    public int binarySearch(int[] nums, int target, boolean bool){
        int left=0;
        int right=nums.length-1;
        int mid=0;
        int tmp=-1;
        while(left<=right)
        {
            mid=(left+right)/2;
            if(nums[mid]==target)
            {
                tmp=mid;
                if (bool){
                    right=mid-1;//将范围向左缩进
                }
                else {
                    left=mid+1;
                }
            }else if(nums[mid]<target)
            {
                left=mid+1;
            }else {
                right=mid-1;
            }
        }
        return tmp;
    }
    public int length(ListNode head){
        int count=0;
        while(head!=null){
            count++;
            head=head.next;
        }
        return count;
    }
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        int length = length(head);
        ListNode cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
    public ListNode removeNthFromEnd1(ListNode head, int n) {
       Stack<ListNode> stack=new Stack<>();
       while (head!=null){
           stack.push(head);
           head=head.next;
       }
       int count=0;
       ListNode node=new ListNode(-1);
       ListNode node1=null;
       while (!stack.isEmpty()){
           ListNode node2=stack.pop();
           count++;
           if (count!=n){
               node2.next=node1;
               node1=node2;
               node.next=node1;
           }
       }
       return node.next;
    }
    public String longestPalindrome(String s) {
        String max="";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                if (isPalindrome(s,i,j)){
                    String str=s.substring(i,j+1);
                    if (max.length()<str.length()){
                        max=str;
                    }
                }else {
                    continue;
                }
            }
        }
        return max;
    }
    List<String> list=new ArrayList<>();
    String max="";
    StringBuilder builder=new StringBuilder();
    public String longestPalindrome1(String s) {
        dfs(s,0);
//        Collections.sort(list,(o1, o2) -> o1.length()-o2.length());
        return max;
    }
    public void dfs(String s,int startIndex){
        if (startIndex>=s.length()){
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome(s,startIndex,i)){
                String str=s.substring(startIndex,i+1);
                if (max.length()<str.length()){
                    max=str;
                }

            }else {
                continue;
            }dfs(s,i+1);
        }
    }
    public boolean isPalindrome(String s,int start,int end){
        if (start>end){
            return false;
        }
        for (int i = start,j=end; i <j; i++,j--) {
            if (s.charAt(i)!=s.charAt(j)){
                return false;
            }
        }
        return true;
    }
    List<List<String>> res=new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] board=new char[n][n];
        for (char[] c : board) {
            Arrays.fill(c, '.');
        }
        backing(board,0);
        return res;
    }
    public void backing(char[][] board,int row){
        if (row==board.length){
            List<String> list=new ArrayList<>();
            for (char[] ch:board) {
                list.add(String.copyValueOf(ch));
            }
            res.add(list);
            return;
        }
        for (int i =0; i < board.length; i++) {
            if (isVailds(board,row,i)){
                board[row][i]='Q';
                backing(board,row+1);
                board[row][i]='.';
            }
        }
    }
    public boolean isVailds(char[][] board,int row,int col){
        if (row==board.length||col==board[0].length){
            return false;
        }
        for (int i = 0; i < row; i++) {
            if (board[i][col]=='Q'){
                return false;
            }
        }
        for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        for(int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
    public int dominantIndex(int[] nums) {
        int max=0;
        int index=-1;
        int second=0;
        for (int i = 0; i < nums.length; i++) {
            if (max<=nums[i]){
                second=max;
                max=nums[i];
                index=i;
            }
           else if (second<nums[i]){
               second=nums[i];
            }
        }
        return max>=second*2?index:-1;
    }
    public void solveSudoku(char[][] board) {
        backijng(board);
    }
    public boolean backijng(char[][] board){
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if (board[i][j]!='.'){
                    continue;
                }
                for (char k='1'; k <='9'; k++) {
                    if (isVaild(board,k,i,j)){
                        board[i][j]=k;
                        if (backijng(board)){
                            return true;
                        }
                        board[i][j]='.';
                    }

                }
                return false;
            }
        }
        return true;
    }
    public boolean isVaild(char[][] board,char k,int x,int y){
        for (int i = 0; i < board.length; i++) {
            if (board[x][i]==k){
                return false;
            }
        }
        for (int i = 0; i < board.length; i++) {
            if (board[i][y]==k){
                return false;
            }
        }
        int startx=(x/3)*3;
        int starty=(y/3)*3;
        for (int i = startx; i < 3+startx; i++) {
            for (int j = starty; j < 3+starty; j++) {
                if (board[i][j] == k ) {
                    return false;
                }
            }
        }
        return true;
    }
}
